home *** CD-ROM | disk | FTP | other *** search
/ 3D GFX / 3D GFX.iso / amiutils / i_l / irit5 / cagd_lib / mshplanr.c < prev    next >
C/C++ Source or Header  |  1995-12-30  |  15KB  |  395 lines
  1. /******************************************************************************
  2. * MshPlanr.c - Test colinearity of control meshes/polygons.              *
  3. *******************************************************************************
  4. * Written by Gershon Elber, Sep. 91.                          *
  5. ******************************************************************************/
  6.  
  7. #include "cagd_loc.h"
  8.  
  9. /*****************************************************************************
  10. * DESCRIPTION:                                                               M
  11. * Computes the distance between two control points at given indices Index?.  M
  12. * Only E2 or E3 point types are supported.                     M
  13. *                                                                            *
  14. * PARAMETERS:                                                                M
  15. *   Points:    To compute the distance between.                              M
  16. *   Index1:    Index of first point to consider.                             M
  17. *   Index2:    Index of second point to consider.                            M
  18. *   PType:     Type of points. Must be E2 or E3                              M
  19. *                                                                            *
  20. * RETURN VALUE:                                                              M
  21. *   CagdRType:    Euclidean distance between the two points.                 M
  22. *                                                                            *
  23. * KEYWORDS:                                                                  M
  24. *   CagdDistanceTwoCtlPts, distance                                          M
  25. *****************************************************************************/
  26. CagdRType CagdDistanceTwoCtlPts(CagdRType **Points,
  27.                 int Index1,
  28.                 int Index2,
  29.                 CagdPointType PType)
  30. {
  31.     switch (PType) {
  32.     case CAGD_PT_E2_TYPE:
  33.         return sqrt(SQR(Points[1][Index1] - Points[1][Index2]) +
  34.             SQR(Points[2][Index1] - Points[2][Index2]));
  35.     case CAGD_PT_E3_TYPE:
  36.         return sqrt(SQR(Points[1][Index1] - Points[1][Index2]) +
  37.             SQR(Points[2][Index1] - Points[2][Index2]) +
  38.             SQR(Points[3][Index1] - Points[3][Index2]));
  39.     default:
  40.         CAGD_FATAL_ERROR(CAGD_ERR_UNSUPPORT_PT);
  41.         return 0.0;
  42.     }
  43. }
  44.  
  45. /*****************************************************************************
  46. * DESCRIPTION:                                                               M
  47. * Fits a plane through the four points from Points indices Index?. Points    M
  48. * may be either E2 or E3 only.                             M
  49. *   Returns 0.0 if failed to fit a plane, otherwise a measure on the size of M
  50. * the mesh data (distance between points) is returned.                 M
  51. *                                                                            *
  52. * PARAMETERS:                                                                M
  53. *   Plane:       To compute and save here.                                   M
  54. *   PType:       Point type expected of four points. Must be E2 or E3.       M
  55. *   Points:      Point array where to look for the four points.              M
  56. *   Index?:      Four indices of the points.                                 M
  57. *                                                                            *
  58. * RETURN VALUE:                                                              M
  59. *   CagdRType:     Measure  on the distance between the data points, 0.0 if  M
  60. *                  fitting failed.                                           M
  61. *                                                                            *
  62. * KEYWORDS:                                                                  M
  63. *   CagdFitPlaneThruCtlPts, plane fit                                        M
  64. *****************************************************************************/
  65. CagdRType CagdFitPlaneThruCtlPts(CagdPlaneStruct *Plane,
  66.                  CagdPointType PType,
  67.                      CagdRType **Points,
  68.                      int Index1,
  69.                  int Index2,
  70.                  int Index3,
  71.                  int Index4)
  72. {
  73.     int i, j, Indices[4];
  74.     CagdRType SizeMeasure,
  75.     MaxDist = 0.0;
  76.     CagdVecStruct V1, V2, V3;
  77.  
  78.     Indices[0] = Index1;
  79.     Indices[1] = Index2;
  80.     Indices[2] = Index3;
  81.     Indices[3] = Index4;
  82.  
  83.     /* Find out the pair of vertices most seperated: */
  84.     for (i = 0; i < 4; i++)
  85.     for (j = i + 1; j < 4; j++) {
  86.         CagdRType
  87.         Dist = CagdDistanceTwoCtlPts(Points, Indices[i], Indices[j],
  88.                                      PType);
  89.         if (Dist > MaxDist) {
  90.         MaxDist = Dist;
  91.         Index1 = i;
  92.         Index2 = j;
  93.         }
  94.     }
  95.  
  96.     if (MaxDist < IRIT_EPSILON)
  97.     return 0.0;
  98.     SizeMeasure = MaxDist;
  99.     MaxDist = 0.0;
  100.  
  101.     /* Find a third most seperated than the selected two. */
  102.     for (i = 0; i < 4; i++)
  103.     if (i != Index1 && i != Index2) {
  104.         CagdRType
  105.         Dist1 = CagdDistanceTwoCtlPts(Points, Indices[Index1],
  106.                           Indices[j], PType),
  107.         Dist2 = CagdDistanceTwoCtlPts(Points, Indices[Index2],
  108.                           Indices[j], PType),
  109.         Dist = MIN(Dist1, Dist2);
  110.  
  111.         if (Dist > MaxDist) {
  112.         MaxDist = Dist;
  113.         Index3 = i;
  114.         }
  115.     }
  116.     if (MaxDist < IRIT_EPSILON)
  117.     return 0.0;
  118.  
  119.     /* Now we have the 3 most seperated vertices to fit a plane thru. */
  120.  
  121.     switch (PType) {
  122.     case CAGD_PT_E2_TYPE:
  123.         /* This is trivial since the plane must be Z = 0. */
  124.         Plane -> Plane[0] = 0.0;
  125.         Plane -> Plane[1] = 0.0;
  126.         Plane -> Plane[2] = 1.0;
  127.         Plane -> Plane[3] = 0.0;
  128.         break;
  129.     case CAGD_PT_E3_TYPE:
  130.         /* Compute normal as a cross product of two vectors thru pts. */
  131.         for (i = 0; i < 3; i++) {
  132.         j = i + 1;
  133.         V1.Vec[i] = Points[j][Index2] - Points[j][Index1];
  134.         V2.Vec[i] = Points[j][Index3] - Points[j][Index2];
  135.         }
  136.         CROSS_PROD(V3.Vec, V1.Vec, V2.Vec);
  137.         CAGD_NORMALIZE_VECTOR(V3);
  138.         for (i = 0; i < 3; i++)
  139.         Plane -> Plane[i] = V3.Vec[i];
  140.  
  141.         Plane -> Plane[3] = (-(V3.Vec[0] * Points[1][Index1] +
  142.                    V3.Vec[1] * Points[2][Index1] +
  143.                    V3.Vec[2] * Points[3][Index1]));
  144.         break;
  145.     default:
  146.         CAGD_FATAL_ERROR(CAGD_ERR_UNSUPPORT_PT);
  147.         break;
  148.     }
  149.  
  150.     return SizeMeasure;
  151. }
  152.  
  153. /*****************************************************************************
  154. * DESCRIPTION:                                                               M
  155. * Computes and returns distance between point Index and given plane which is M
  156. * assumed to be normalized, so that the A B C plane;s normal has a unit      M
  157. * length.                                                             M
  158. *   Also assumes the Points are non rational with MaxDim dimension.         M
  159. *                                                                            *
  160. * PARAMETERS:                                                                M
  161. *   Plane:      To compute the distance to.                                  M
  162. *   Points:     To compute the distance from.                                M
  163. *   Index:      Index in Points for the point to consider.                   M
  164. *   MaxDim:     Number of dimensions to consider. Less or equal to three.    M
  165. *                                                                            *
  166. * RETURN VALUE:                                                              M
  167. *   CagdRType:   Resulting distance.                                         M
  168. *                                                                            *
  169. * KEYWORDS:                                                                  M
  170. *   CagdDistPtPlane, point plane distance                                    M
  171. *****************************************************************************/
  172. CagdRType CagdDistPtPlane(CagdPlaneStruct *Plane,
  173.               CagdRType **Points,
  174.               int Index,
  175.               int MaxDim)
  176. {
  177.     int i;
  178.     CagdRType
  179.     R = Plane -> Plane[3];
  180.  
  181.     for (i = 0; i < MaxDim; i++)
  182.     R += Plane -> Plane[i] * Points[i + 1][Index];
  183.  
  184.     return fabs(R);
  185. }
  186.  
  187. /*****************************************************************************
  188. * DESCRIPTION:                                                               *
  189. * Computes and returns distance between point Index and the line from point  *
  190. * index 0 in direction LineDir (usually the line direction to last the       *
  191. * point).                                                                    *
  192. *   LineDir is assumed to be unit length normalized vector.             *
  193. *                                                                            *
  194. * PARAMETERS:                                                                *
  195. *   LineDir:    To compute distance to.                                      *
  196. *   Plane:      To compute the distance to.                                  *
  197. *   Points:     To compute the distance from.                                *
  198. *   Index:      Index in Points for the point to consider.                   *
  199. *   MaxDim:     Number of dimensions to consider. Less or equal to three.    *
  200. *                                                                            *
  201. * RETURN VALUE:                                                              M
  202. *   CagdRType:   Resulting distance.                                         M
  203. *****************************************************************************/
  204. static CagdRType CagdDistPtLine(CagdVecStruct *LineDir,
  205.                 CagdRType **Points,
  206.                 int Index,
  207.                 int MaxDim)
  208. {
  209.     int i;
  210.     CagdRType R;
  211.     CagdVecStruct V1, V2;
  212.  
  213.     for (i = 0; i < MaxDim; i++)
  214.     V1.Vec[i] = Points[i+1][Index] - Points[i+1][0];
  215.     if (MaxDim < 3)
  216.     V1.Vec[2] = 0.0;
  217.  
  218.     /* Let V1 be the vector from point zero to point index. Then the distance */
  219.     /* from point Index the the line is: | (LineDir . V1) LineDir - V1 |.     */
  220.     V2 = *LineDir;
  221.     R = DOT_PROD(V1.Vec, V2.Vec);
  222.     CAGD_MULT_VECTOR(V2, R);
  223.     CAGD_SUB_VECTOR(V2, V1);
  224.  
  225.     return CAGD_LEN_VECTOR(V2);
  226. }
  227.  
  228. /*****************************************************************************
  229. * DESCRIPTION:                                                               M
  230. * Tests polygonal colinearity by testing the distance of interior control    M  
  231. * points from the line connecting the two control polygon end points.         M
  232. *   Returns a relative ratio of deviation from line relative to its length.  M
  233. *   Zero means all points are colinear.                         M
  234. *   If two end points are same ( no line can be fit ) INFINITY is returned.  M
  235. *                                                                            *
  236. * PARAMETERS:                                                                M
  237. *   Crv:       To measure its colinearity.                                   M
  238. *                                                                            *
  239. * RETURN VALUE:                                                              M
  240. *   CagdRType:    Colinearity relative measure.                              M
  241. *                                                                            *
  242. * KEYWORDS:                                                                  M
  243. *   CagdEstimateCrvColinearity, conversion, colinearity                      M
  244. *****************************************************************************/
  245. CagdRType CagdEstimateCrvColinearity(CagdCrvStruct *Crv)
  246. {
  247.     int i,
  248.     MaxDim = 3,
  249.     Length = Crv -> Length,
  250.     Length1 = Length - 1;
  251.     CagdRType LineLen,
  252.     MaxDist = 0.0,
  253.     **Points = Crv -> Points;
  254.     CagdCrvStruct
  255.     *CoercedCrv = NULL;
  256.     CagdPointType
  257.     PType = Crv ->PType;
  258.     CagdVecStruct LineDir;
  259.  
  260.     switch (PType) {          /* Convert the rational cases to non rational. */
  261.     case CAGD_PT_P2_TYPE:
  262.         CoercedCrv = CagdCoerceCrvTo(Crv, CAGD_PT_E2_TYPE);
  263.         Points = CoercedCrv -> Points;
  264.         PType = CoercedCrv -> PType;
  265.         break;
  266.     case CAGD_PT_P3_TYPE:
  267.         CoercedCrv = CagdCoerceCrvTo(Crv, CAGD_PT_E3_TYPE);
  268.         Points = CoercedCrv -> Points;
  269.         PType = CoercedCrv -> PType;
  270.         break;
  271.     default:
  272.         break;
  273.     }
  274.  
  275.     switch (PType) {
  276.     case CAGD_PT_E2_TYPE:
  277.         LineDir.Vec[0] = Points[1][Length1] - Points[1][0];
  278.         LineDir.Vec[1] = Points[2][Length1] - Points[2][0];
  279.         LineDir.Vec[2] = 0.0;
  280.         MaxDim = 2;
  281.         break;
  282.     case CAGD_PT_E3_TYPE:
  283.         LineDir.Vec[0] = Points[1][Length1] - Points[1][0];
  284.         LineDir.Vec[1] = Points[2][Length1] - Points[2][0];
  285.         LineDir.Vec[2] = Points[3][Length1] - Points[3][0];
  286.         break;
  287.     default:
  288.         CAGD_FATAL_ERROR(CAGD_ERR_UNSUPPORT_PT);
  289.         break;
  290.     }
  291.  
  292.     LineLen = CAGD_LEN_VECTOR(LineDir);
  293.     if (LineLen < IRIT_EPSILON) {
  294.     if (CoercedCrv != NULL)
  295.         CagdCrvFree(CoercedCrv);
  296.     return INFINITY;
  297.     }
  298.  
  299.     CAGD_DIV_VECTOR(LineDir, LineLen);
  300.  
  301.     for (i = 1; i < Length1; i++) {
  302.     CagdRType
  303.         Dist = CagdDistPtLine(&LineDir, Points, i, MaxDim);
  304.  
  305.     if (Dist > MaxDist)
  306.         MaxDist = Dist;
  307.     }
  308.  
  309.     if (CoercedCrv != NULL)
  310.     CagdCrvFree(CoercedCrv);
  311.  
  312.     return MaxDist / LineLen;
  313. }
  314.  
  315. /*****************************************************************************
  316. * DESCRIPTION:                                                               M
  317.  Tests mesh colinearity by testing the distance of interior points from the  M
  318. * plane thru 3 corner points.                             M
  319. *   Returns a relative ratio of deviation from plane relative to its size.   M
  320. *   Zero means all points are coplanar.                         M
  321. *   If end points are same ( no plane can be fit ) INFINITY is returned.     M
  322. *                                                                            M
  323. * PARAMETERS:                                                                M
  324. *   Srf:        To measure its coplanarity.                                  M
  325. *                                                                            *
  326. * RETURN VALUE:                                                              M
  327. *   CagdRType:    Coplanarity measure.                                       M
  328. *                                                                            *
  329. * KEYWORDS:                                                                  M
  330. *   CagdEstimateSrfPlanarity, conversion, coplanarity                        M
  331. *****************************************************************************/
  332. CagdRType CagdEstimateSrfPlanarity(CagdSrfStruct *Srf)
  333. {
  334.     int i,
  335.     ULength = Srf -> ULength,
  336.     ULength1 = ULength - 1,
  337.     VLength = Srf -> VLength,
  338.     VLength1 = VLength - 1;
  339.     CagdRType
  340.     PlaneSize = 0.0,
  341.     MaxDist = 0.0,
  342.     **Points = Srf -> Points;
  343.     CagdSrfStruct
  344.     *CoercedSrf = NULL;
  345.     CagdPointType
  346.     PType = Srf ->PType;
  347.     CagdPlaneStruct Plane;
  348.  
  349.     switch (PType) {          /* Convert the rational cases to non rational. */
  350.     case CAGD_PT_P2_TYPE:
  351.     case CAGD_PT_E2_TYPE:
  352.         /* Trivial case - it is planar surface. */
  353.         return 0.0;
  354.     case CAGD_PT_P3_TYPE:
  355.         CoercedSrf = CagdCoerceSrfTo(Srf, CAGD_PT_E3_TYPE);
  356.         Points = CoercedSrf -> Points;
  357.         PType = CoercedSrf -> PType;
  358.         break;
  359.     default:
  360.         break;
  361.     }
  362.  
  363.     switch (PType) {
  364.     case CAGD_PT_E3_TYPE:
  365.         PlaneSize = CagdFitPlaneThruCtlPts(&Plane, PType, Points,
  366.                     CAGD_MESH_UV(Srf, 0,        0),
  367.                     CAGD_MESH_UV(Srf, 0,        VLength1),
  368.                     CAGD_MESH_UV(Srf, ULength1, 0),
  369.                     CAGD_MESH_UV(Srf, ULength1, VLength1));
  370.         break;
  371.     default:
  372.         CAGD_FATAL_ERROR(CAGD_ERR_UNSUPPORT_PT);
  373.         break;
  374.     }
  375.  
  376.     if (PlaneSize < IRIT_EPSILON) {
  377.     if (CoercedSrf != NULL)
  378.         CagdSrfFree(CoercedSrf);
  379.     return INFINITY;
  380.     }
  381.  
  382.     for (i = ULength * VLength; i > 0; i--) {
  383.     CagdRType
  384.         Dist = CagdDistPtPlane(&Plane, Points, i, 3);
  385.  
  386.     if (Dist > MaxDist)
  387.         MaxDist = Dist;
  388.     }
  389.  
  390.     if (CoercedSrf != NULL)
  391.     CagdSrfFree(CoercedSrf);
  392.  
  393.     return MaxDist / PlaneSize;
  394. }
  395.